package com.yangzhe.algorithm.c036;

import java.util.ArrayList;
import java.util.List;

// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
public class Code02_ZigzagLevelOrderTraversal_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    private static TreeNode[] queue = new TreeNode[2001];

    private static int l, r = 0;

    /**
     * 使用优化过的BFS，可以知道每次处理的层
     * 1. 根节点加入队列
     * 3. 开始循环 队列不为空时
     * 3.1 记录队列size
     * 3.2 开始循环size-第一次-把打印的过程拆出来，一次正序一次反序
     * 2.2.1 如果正序，则打印l + i位置
     * 3.2.2 如果逆序，则打印r - 1 -i位置（队列中r是队尾下一个位置）
     * <p>
     * 3.3 开始循环size次-第二次-记录下一层-不打印
     * 3.3.1 弹出节点
     * 3.3.2 左不为空 加入队列
     * 3.3.3 右不为空 加入队列
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        l = r = 0;
        if (root != null) {
            queue[r++] = root;
            boolean reverse = false;
            while (l != r) {
                int size = r - l;
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    int index;
                    if (reverse) {
                        index = r - 1 - i;
                    } else {
                        index = l + i;
                    }
                    TreeNode treeNode = queue[index];
                    list.add(treeNode.val);
                }


                for (int i = 0; i < size; i++) {
                    TreeNode treeNode = queue[l++];

                    if (treeNode.left != null) {
                        queue[r++] = treeNode.left;
                    }

                    if (treeNode.right != null) {
                        queue[r++] = treeNode.right;
                    }
                }

                reverse = !reverse;
                result.add(list);
            }
        }

        return result;
    }

}
